{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Binary Tree II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: insertIntoMaxTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大二叉树 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>最大树</strong> 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。</p>\n",
    "\n",
    "<p>给你最大树的根节点 <code>root</code> 和一个整数 <code>val</code> 。</p>\n",
    "\n",
    "<p>就像 <a href=\"https://leetcode.cn/problems/maximum-binary-tree/\" target=\"_blank\">之前的问题</a> 那样，给定的树是利用 <code>Construct(a)</code>&nbsp;例程从列表&nbsp;<code>a</code>（<code>root = Construct(a)</code>）递归地构建的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>a</code> 为空，返回&nbsp;<code>null</code> 。</li>\n",
    "\t<li>否则，令&nbsp;<code>a[i]</code> 作为 <code>a</code> 的最大元素。创建一个值为&nbsp;<code>a[i]</code>&nbsp;的根节点 <code>root</code> 。</li>\n",
    "\t<li><code>root</code>&nbsp;的左子树将被构建为&nbsp;<code>Construct([a[0], a[1], ..., a[i - 1]])</code> 。</li>\n",
    "\t<li><code>root</code>&nbsp;的右子树将被构建为&nbsp;<code>Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]])</code> 。</li>\n",
    "\t<li>返回&nbsp;<code>root</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请注意，题目没有直接给出 <code>a</code> ，只是给出一个根节点&nbsp;<code>root = Construct(a)</code> 。</p>\n",
    "\n",
    "<p>假设 <code>b</code> 是 <code>a</code> 的副本，并在末尾附加值 <code>val</code>。题目数据保证 <code>b</code> 中的值互不相同。</p>\n",
    "\n",
    "<p>返回&nbsp;<code>Construct(b)</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-1-1.png\" style=\"height: 160px; width: 159px;\" /><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-1-2.png\" style=\"height: 160px; width: 169px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,1,3,null,null,2], val = 5\n",
    "<strong>输出：</strong>[5,4,null,1,3,null,null,2]\n",
    "<strong>解释：</strong>a = [1,4,2,3], b = [1,4,2,3,5]</pre>\n",
    "\n",
    "<p><strong>示例 2：<br />\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-2-1.png\" style=\"height: 160px; width: 180px;\" /><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-2-2.png\" style=\"height: 160px; width: 214px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,2,4,null,1], val = 3\n",
    "<strong>输出：</strong>[5,2,4,null,1,null,3]\n",
    "<strong>解释：</strong>a = [2,1,5,4], b = [2,1,5,4,3]</pre>\n",
    "\n",
    "<p><strong>示例 3：<br />\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-3-1.png\" style=\"height: 160px; width: 180px;\" /><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-3-2.png\" style=\"height: 160px; width: 201px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,2,3,null,1], val = 4\n",
    "<strong>输出：</strong>[5,2,4,null,1,3]\n",
    "<strong>解释：</strong>a = [2,1,5,3], b = [2,1,5,3,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 100]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 100</code></li>\n",
    "\t<li>树中的所有值 <strong>互不相同</strong></li>\n",
    "\t<li><code>1 &lt;= val &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-binary-tree-ii](https://leetcode.cn/problems/maximum-binary-tree-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-binary-tree-ii](https://leetcode.cn/problems/maximum-binary-tree-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,3,null,null,2]\\n5', '[5,2,4,null,1]\\n3', '[5,2,3,null,1]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        #边界条件\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        #对于构建好的树，只需要估计他的右孩子和val之间的关系\n",
    "        if val > root.val:\n",
    "            new_root = TreeNode(val)\n",
    "            new_root.left = root\n",
    "            return new_root\n",
    "        \n",
    "        root.right = self.insertIntoMaxTree(root.right,val)\n",
    "        return root\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        def constructMaximumBinaryTree(nums: List[int]) -> Optional[TreeNode]:\n",
    "            if nums == []:\n",
    "                return None\n",
    "            else:\n",
    "                a=nums.index(max(nums))\n",
    "                curroot=TreeNode(val=nums[a])\n",
    "                leftnums=nums[:a]\n",
    "                rightnums=nums[a+1:]\n",
    "                curroot.left=constructMaximumBinaryTree(leftnums)\n",
    "                curroot.right=constructMaximumBinaryTree(rightnums)\n",
    "                return curroot\n",
    "        nums=[]\n",
    "        def dfs(root1):\n",
    "            if root1 is None:\n",
    "                return \n",
    "            else:\n",
    "                dfs(root1.left)\n",
    "                nums.append(root1.val)\n",
    "                dfs(root1.right)\n",
    "        dfs(root)\n",
    "        nums.append(val)\n",
    "        return constructMaximumBinaryTree(nums)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 如果大于，往右走，如果小于，把当前节点作为它的子节点并代替这个节点的位置，如果当前为None，直接代替\n",
    "        node = TreeNode(val)\n",
    "        if root.val < val:\n",
    "            node.left = root\n",
    "            return node\n",
    "        \n",
    "        cur = root\n",
    "        while True:\n",
    "            if cur.right == None:\n",
    "                cur.right = node\n",
    "                return root\n",
    "            elif cur.right.val < val:\n",
    "                node.left = cur.right\n",
    "                cur.right = node\n",
    "                return root\n",
    "            else:\n",
    "                cur = cur.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root or root.val < val:\n",
    "            ans = TreeNode(val)\n",
    "            ans.left = root\n",
    "            return ans\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 如果当前数为空，直接返回以val为值的树\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            temp = root\n",
    "            root = TreeNode(val)\n",
    "            root.left = temp\n",
    "        else:\n",
    "            root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root or root.val < val:\n",
    "            return TreeNode(val, root)\n",
    "\n",
    "        # 只会更新右子树\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root or val > root.val:\n",
    "            return TreeNode(val, left = root)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            temp = root\n",
    "            root = TreeNode(val)\n",
    "            root.left = temp\n",
    "        else:\n",
    "            root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # if not root:\n",
    "        #     return TreeNode(val, None, None)\n",
    "        # if root.val < val:\n",
    "        #     return TreeNode(val, root, None)\n",
    "        # elif root.val > val:\n",
    "        #     return self.insertIntoMaxTree(root.left, val)\n",
    "        # return self.insertIntoMaxTree(root.right, val)\n",
    "        if root is None:\n",
    "            root = TreeNode(val, None, None)\n",
    "            return root\n",
    "        if val > root.val:\n",
    "            return TreeNode(val, root, None)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        def dfs(root, val):\n",
    "            if not root:\n",
    "                return TreeNode(val)\n",
    "            if root.val < val:\n",
    "                return TreeNode(val, root, None)\n",
    "            root.right = dfs(root.right, val)\n",
    "            return root\n",
    "        return dfs(root, val)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            return TreeNode(val, root, None)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root or root.val < val:\n",
    "            return TreeNode(val, root)\n",
    "        \n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root: return TreeNode(val)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return []\n",
    "            return dfs(node.left) + [node.val] + dfs(node.right)\n",
    "        \n",
    "        trees = dfs(root) + [val]\n",
    "\n",
    "        def dfs2(lst):\n",
    "            if not lst: return None\n",
    "            \n",
    "            _max = max(lst)\n",
    "            idx = lst.index(_max)\n",
    "            return TreeNode(val=_max,\n",
    "                            left=dfs2(lst[:idx]),\n",
    "                            right=dfs2(lst[idx+1:]))\n",
    "\n",
    "        return dfs2(trees)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root: return TreeNode(val)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return []\n",
    "            return dfs(node.left) + [node.val] + dfs(node.right)\n",
    "        \n",
    "        trees = dfs(root) + [val]\n",
    "\n",
    "        def dfs2(lst):\n",
    "            if not lst: return None\n",
    "            \n",
    "            _max = max(lst)\n",
    "            idx = lst.index(_max)\n",
    "            return TreeNode(val=_max,\n",
    "                            left=dfs2(lst[:idx]),\n",
    "                            right=dfs2(lst[idx+1:]))\n",
    "\n",
    "        return dfs2(trees)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 分为三种情况考虑：\n",
    "        # 1.根节点的值小于给定的整数 val，那么新的树会以 val 作为根节点，并将原来的树作为新的根节点的左子树。\n",
    "        # 2.当我们遍历到节点 cur 以及它的父节点 parent，并且 cur 节点的值小于 val 时，我们就可以停止遍历，构造一个新的节点，以 val 为值且以 cur 为左子树。我们将该节点作为 parent 的新的右节点，并返回根节点作为答案即可。\n",
    "        # 3. 如果遍历完成之后，仍然没有找到比 val 值小的节点，那么我们构造一个新的节点，以 valval 为值，将该节点作为 parent 的右节点，并返回根节点作为答案即可。\n",
    "\n",
    "        # 如果树为空，直接返回新节点\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        # 如果插入值大于根节点的值，将新节点作为新根节点，原根节点成为新根节点的左子树\n",
    "        if val > root.val:\n",
    "            new_root = TreeNode(val)\n",
    "            new_root.left = root\n",
    "            return new_root\n",
    "\n",
    "        # 否则，递归地插入到右子树\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            return TreeNode(val, root)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            return TreeNode(val, left=root)\n",
    "        node = root\n",
    "        while node and node.val > val:\n",
    "            pre = node\n",
    "            node = node.right\n",
    "        newnode = TreeNode(val, left=node)\n",
    "        pre.right = newnode\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "\n",
    "        if root.val < val:\n",
    "            new_root = TreeNode(val)\n",
    "            new_root.left = root \n",
    "            return new_root \n",
    "\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            return TreeNode(val, root)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int):\n",
    "        new_node = TreeNode(val)\n",
    "        if root is None:\n",
    "            return new_node\n",
    "        if root.val > val:\n",
    "            root.right = self.insertIntoMaxTree(root.right, val)\n",
    "            return root\n",
    "        new_node.left = root\n",
    "        return new_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "\n",
    "\n",
    "        def dfs(parent, node):\n",
    "            if not node:\n",
    "                parent.right = TreeNode(val)\n",
    "                return\n",
    "\n",
    "            if val > node.val:\n",
    "                parent.right = TreeNode(val)\n",
    "                parent.right.left = node\n",
    "            else:\n",
    "                dfs(node, node.right)\n",
    "\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "\n",
    "        if val > root.val:\n",
    "            return TreeNode(val, left=root)\n",
    "        \n",
    "        dfs(root, root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        a=list()\n",
    "        def find(root):\n",
    "            if root==None:\n",
    "                return\n",
    "            find(root.left)\n",
    "            a.append(root.val)\n",
    "            find(root.right)\n",
    "        find(root)\n",
    "        a.append(val)\n",
    "        def build(l):\n",
    "            if l==[]:\n",
    "                return None\n",
    "            m=0\n",
    "            mid=0\n",
    "            for i in range(len(l)):\n",
    "                if m<l[i]:\n",
    "                    m=max(m,l[i])\n",
    "                    mid=i\n",
    "            A=TreeNode()\n",
    "            A.val=m\n",
    "            A.left=build(l[:mid])\n",
    "            A.right=build(l[mid+1:])\n",
    "            return A\n",
    "        return build(a)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        node = TreeNode(val)\n",
    "        prev = None\n",
    "        cur = root\n",
    "        # 遍历root 往右子树遍历\n",
    "        while cur and cur.val>val:\n",
    "            # 记录当前结点的父节点\n",
    "            prev = cur\n",
    "            cur = cur.right\n",
    "        # 如果val大于原树的最大值\n",
    "        if not prev:\n",
    "            node.left = cur\n",
    "            return node\n",
    "        # 遍历到了右子树合适的位置 换结点\n",
    "        else:\n",
    "            # \n",
    "            prev.right = node\n",
    "            node.left = cur\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 分为两种情况考虑：\n",
    "        \n",
    "        # 如果树为空，直接返回新节点\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        # 如果插入值大于根节点的值，将新节点作为新根节点，原根节点成为新根节点的左子树\n",
    "        if val > root.val:\n",
    "            new_root = TreeNode(val)\n",
    "            new_root.left = root\n",
    "            return new_root\n",
    "\n",
    "        # 否则，递归地插入到右子树\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root or root.val < val:\n",
    "            return TreeNode(val, root)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root.val < val:\n",
    "            res = TreeNode(val)\n",
    "            res.left = root\n",
    "            return res\n",
    "        \n",
    "        if not root.right:\n",
    "            root.right = TreeNode(val)\n",
    "            return root\n",
    "\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 如果大于，往右走，如果小于，把当前节点作为它的子节点并代替这个节点的位置，如果当前为None，直接代替\n",
    "        node = TreeNode(val)\n",
    "        if root.val < val:\n",
    "            node.left = root\n",
    "            return node\n",
    "        \n",
    "        cur = root\n",
    "        while True:\n",
    "            if cur.right == None:\n",
    "                cur.right = node\n",
    "                return root\n",
    "            elif cur.right.val < val:\n",
    "                node.left = cur.right\n",
    "                cur.right = node\n",
    "                return root\n",
    "            else:\n",
    "                cur = cur.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            node = TreeNode(val)\n",
    "            node.left = root\n",
    "            return node\n",
    "        # root.val > val ,同时为了保证是在最后，只能在右边子树开始尝试，除非右子树为空\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        def build_tree(node, val):\n",
    "            if node.right is not None and node.right.val < val:\n",
    "                node.right = TreeNode(val, node.right, None)\n",
    "            elif node.right:\n",
    "                node.right = build_tree(node.right, val)\n",
    "            else:\n",
    "                node.right = TreeNode(val, None, None)\n",
    "            return node\n",
    "        if root.val < val:\n",
    "            return TreeNode(val, root, None)\n",
    "        build_tree(root,val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return TreeNode(val)\n",
    "\n",
    "        if root.val < val:\n",
    "            temp = root\n",
    "            root = TreeNode(val)\n",
    "            root.left = temp\n",
    "        \n",
    "        else:\n",
    "            root.right = self.insertIntoMaxTree(root.right, val)\n",
    "\n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root.val < val:\n",
    "            node = TreeNode(val)\n",
    "            node.left = root\n",
    "            return node\n",
    "            \n",
    "        if not root.right:\n",
    "            node = TreeNode(val)\n",
    "            root.right = node\n",
    "            return root\n",
    "\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root: return TreeNode(val)\n",
    "        elif val > root.val:\n",
    "            new = TreeNode(val)\n",
    "            new.left = root\n",
    "            return new\n",
    "        else:\n",
    "            root.right = self.insertIntoMaxTree(root.right, val)\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        node=TreeNode(val)\n",
    "        prev,cur=None,root\n",
    "        while cur!=None and cur.val >val:\n",
    "            prev=cur\n",
    "            cur=cur.right\n",
    "        if prev is None:\n",
    "            node.left=cur\n",
    "            return node\n",
    "        else:\n",
    "            prev.right=node\n",
    "            node.left=cur\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root or val>root.val:return TreeNode(val, root)\n",
    "        root.right=self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        parent,current=None,root\n",
    "        while current:\n",
    "            if val>current.val:\n",
    "                if not parent:\n",
    "                    return TreeNode(val,root,None)\n",
    "                node=TreeNode(val,current,None)\n",
    "                parent.right=node\n",
    "                return root\n",
    "            else:\n",
    "                parent=current\n",
    "                current=current.right\n",
    "\n",
    "        parent.right=TreeNode(val)\n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:  # 如果最大二叉树的根节点为空，那么直接返回val结点\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:  # 如果最大二叉树的根节点小于val结点 且 val是最大二叉树数组的末尾附加值，所以直接构建val的左子树为root\n",
    "            return TreeNode(val, root, None)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)  # 如果最大二叉树的结点值大于val结点，说明val要被插入该最大二叉树的右子树中\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # nn = TreeNode(val)\n",
    "        # dummy = TreeNode(-1,None, root)\n",
    "\n",
    "        # def run(node = dummy):\n",
    "        #     if not node.right or node.right.val < val:\n",
    "        #         node.right, nn.left = nn, node.right\n",
    "        #         return\n",
    "        #     run(node.right)\n",
    "        \n",
    "        # run()\n",
    "        # return dummy.right\n",
    "        if (not root or root.val < val): return TreeNode(val, root, None)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            temp = root\n",
    "            root = TreeNode(val)\n",
    "            root.left = temp\n",
    "        else:\n",
    "            root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root or root.val < val:\n",
    "            return TreeNode(val, root)\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 遍历右子节点的过程\n",
    "        parent,cur=None,root\n",
    "        while cur: \n",
    "            if val>cur.val: \n",
    "                if not parent: \n",
    "                    return TreeNode(val,root,None) # 比根节点大，退出\n",
    "                node=TreeNode(val,cur,None)\n",
    "                parent.right=node\n",
    "                return root # 不是比根节点大，最后返回根节点这颗树\n",
    "            else:\n",
    "                parent=cur # 不断向右子树遍历\n",
    "                cur=cur.right\n",
    "        parent.right=TreeNode(val)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if(root==None):\n",
    "            return TreeNode(val)\n",
    "        if(root.val<val):\n",
    "            new_root = TreeNode(val = val)\n",
    "            new_root.left = root\n",
    "            return new_root\n",
    "        if(root.val>val):\n",
    "            root.right = self.insertIntoMaxTree(root.right,val)\n",
    "        return root\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 如果大于，往右走，如果小于，把当前节点作为它的子节点并代替这个节点的位置，如果当前为None，直接代替\n",
    "        node = TreeNode(val)\n",
    "        if root.val < val:\n",
    "            node.left = root\n",
    "            return node\n",
    "        \n",
    "        cur = root\n",
    "        while r := cur.right:\n",
    "            if r.val < val:\n",
    "                node.left = r\n",
    "                cur.right = node\n",
    "                return root\n",
    "            else:\n",
    "                cur = cur.right\n",
    "\n",
    "        cur.right = node\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root: return TreeNode(val)\n",
    "        if root.val < val:\n",
    "            head = TreeNode(val)\n",
    "            head.left = root\n",
    "            return head\n",
    "        root.right = self.insertIntoMaxTree(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        node = TreeNode(val)\n",
    "        prev = None\n",
    "        cur = root\n",
    "        # 遍历root 往右子树遍历\n",
    "        while cur:\n",
    "            if cur.val > val:\n",
    "                # 记录当前结点的父节点\n",
    "                prev = cur\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                break\n",
    "        # 如果val大于原树的最大值\n",
    "        if not prev:\n",
    "            node.left = cur\n",
    "            return node\n",
    "        # 遍历到了右子树合适的位置 换结点\n",
    "        else:\n",
    "            # \n",
    "            prev.right = node\n",
    "            node.left = cur\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # 遍历右子节点的过程\n",
    "        parent,cur=None,root\n",
    "        while cur: \n",
    "            if val>cur.val: \n",
    "                if not parent: \n",
    "                    return TreeNode(val,root,None) # 比根节点大，退出\n",
    "                node=TreeNode(val,cur,None)\n",
    "                parent.right=node\n",
    "                return root # 不是比根节点大，最后返回根节点这颗树\n",
    "            else:\n",
    "                parent=cur # 不断向右子树遍历\n",
    "                cur=cur.right\n",
    "        parent.right=TreeNode(val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "      if val > root.val:\n",
    "        return TreeNode(val, left=root)\n",
    "\n",
    "      def walk(parent, child):\n",
    "        if not child:\n",
    "          parent.right = TreeNode(val)\n",
    "          return\n",
    "\n",
    "        if val > child.val:\n",
    "          node = TreeNode(val)\n",
    "          node.left = child\n",
    "          parent.right = node\n",
    "          return\n",
    "\n",
    "        walk(child, child.right)\n",
    "\n",
    "      walk(root, root.right)\n",
    "      return root\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        #先恢复成数组，然后按照要求生成树\n",
    "        def recover_nums(root):\n",
    "            if root is None:\n",
    "                return []\n",
    "            cur = [root.val]\n",
    "            left = recover_nums(root.left)\n",
    "            right = recover_nums(root.right)\n",
    "            return left + cur + right\n",
    "        \n",
    "        #构建最大二叉树\n",
    "        def construct(nums):\n",
    "            if nums == []:\n",
    "                return None\n",
    "            max_num = max(nums)\n",
    "            max_idx = nums.index(max_num)\n",
    "            root = TreeNode(max_num)\n",
    "            root.left = construct(nums[:max_idx])\n",
    "            root.right = construct(nums[max_idx+1:])\n",
    "            return root\n",
    "\n",
    "        nums = recover_nums(root)\n",
    "        nums.append(val)\n",
    "        return construct(nums)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
